package com.zrkizzy.linkedlist;

/**
 * 707. 设计链表 <p>
 *
 * @author zhangrongkang
 * @since 2022/11/14
 * @see <a href="https://leetcode.cn/problems/design-linked-list/description/">https://leetcode.cn/problems/design-linked-list/description/</a>
 */
public class 设计链表 {

    class MyLinkedList {
        /**
         * 定义链表的节点
         */
        class Node {
            public int val;
            public Node next;

            public Node(int val) {
                this.val = val;
            }
        }

        /**
         * 默认单链表头节点
         */
        private Node head;
        /**
         * 链表长度
         */
        private int length;

        /**
         * 初始化链表
         */
        public MyLinkedList() {
            // 初始化链表的虚拟节点
            head = new Node(0);
            // 初始化链表长度
            length = 0;
        }

        /**
         * 获取链表指定位置的值
         *
         * @param index 指定索引
         * @return 指定索引位置的值
         */
        public int get(int index) {
            // 越界判断
            if (index < 0 || index >= length) {
                return -1;
            }
            Node node = head;
            // 寻找第index个节点
            for (int i = 0; i <= index; i++) {
                node = node.next;
            }
            // 退出循环后，当前的node就是想要获取到的节点
            return node.val;
        }

        /**
         * 添加头节点
         *
         * @param val 头节点存储的值
         */
        public void addAtHead(int val) {
            // 复用已经实现的方法
            addAtIndex(0, val);
        }

        /**
         * 添加尾节点
         *
         * @param val 尾节点存储的值
         */
        public void addAtTail(int val) {
            // 复用已经实现的方法
            addAtIndex(length, val);
        }

        /**
         * 向指定索引位置插入节点
         *
         * @param index 指定索引位置
         * @param val 指定节点的值
         */
        public void addAtIndex(int index, int val) {
            // 不会插入链表节点的情况
            if (index > length) {
                return;
            }
            // 需要插入到头节点的情况
            if (index < 0) {
                index = 0;
            }
            // 定义新的节点
            Node node = new Node(val);
            Node pre = head;
            // 找到当前位置的前一个节点
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            node.next = pre.next;
            pre.next = node;
            // 维护链表长度
            length++;
        }

        /**
         * 删除指定位置的节点
         *
         * @param index 指定索引位置
         */
        public void deleteAtIndex(int index) {
            if (index < 0 || index >= length) {
                return;
            }
            // 维护链表长度
            length--;
            // 删除头节点的情况
            if (index == 0) {
                head = head.next;
                return;
            }
            Node cur = head;
            // 找到当前要删除的节点的前一个位置
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
    }
}
